#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        vector<vector<unsigned long long>> dp(n+1,vector<unsigned long long>(amount+1));
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=amount;j++)
            {
                dp[i][j]+=dp[i-1][j];
                if(j-coins[i-1]>=0)
                    dp[i][j]+=dp[i][j-coins[i-1]];
            }
        }
        return dp[n][amount];
    }
};